class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        ranges = []
        for word in wordDict:
            begin = 0
            while True:
                begin = s.find(word, begin)
                if begin == -1:
                    break
                end = begin + len(word)-1
                ranges.append((begin, end))
                begin += 1
        ranges.sort(key=lambda x: x[1])

        dp = {-1:[-1]}
        for ran in ranges:
            if ran[0]-1 in dp:
                if ran[1] not in dp:
                    dp.update({ran[1]:[]})
                dp[ran[1]].append(ran[0]-1)
        result = []
        def traverse(ending, tmpStr):
            if ending == -1:
                result.append(tmpStr.strip())
            else:
                for lastEnding in dp[ending]:
                    localTmpStr = str(s[lastEnding+1 : ending+1]) + " " + tmpStr
                    traverse(lastEnding, localTmpStr)
        if len(s)-1 in dp:
            traverse(len(s)-1, "")
        return result

print(Solution().wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"]))